package org.example.leetcode;

/**
 * file:ErChaShu.class
 * function:二叉树算法练习
 *
 * @author shaodan wang
 * @date 2024-07-15
 */


import org.junit.jupiter.api.Test;

/**
 * 树的节点
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class ErChaShu {

    /**
     * 路径总和
     * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。
     * 判断该树中是否存在
     * 根节点到叶子节点 的路径，
     * 这条路径上所有节点值相加等于目标和 targetSum 。
     * 如果存在，返回 true ；否则，返回 false 。
     * @param root
     * @param targetSum
     * @return
     */


    private  Boolean hasPathSum = false;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        travelTree(root,0,targetSum);
        return hasPathSum;
    }



    public void travelTree(TreeNode root,int sum,int targetSum){
        if(root == null){
            return;
        }
        sum = sum + root.val;

        if(root.left == null && root.right == null && targetSum == sum){
            hasPathSum = true;
            return;
        }else if((root.left == null) && (root.right ==  null)){
            sum = 0;
        }
        travelTree(root.left,sum,targetSum);
        travelTree(root.right,sum,targetSum);
    }

    public boolean hasPathSum1(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        if(root.val - targetSum == 0 && root.left == null && root.right == null){
            return true;
        }else {
            return hasPathSum1(root.left, targetSum - root.val) || hasPathSum1(root.right,targetSum - root.val);
        }
    }
    @Test
    public void test001(){
    }



}
